package Sort;

import java.util.Random;

/**
 * 1.从序列中随机挑出一个元素,作为基准
 * 2.重新排列序列,将所有比基准值小的元素摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边)。
 *  这个操作结束之后,该基准就处于数列的中间位置。这个称为分区操作;
 * 3.递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
 */
public class QuickSort {

    private static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int Partition(int[] arr, int left, int right){
        if (left == right){
            return left;
        }

        int pivot = (int) (left + Math.random() * (right - left + 1));
        swap(arr, pivot, right);
        int small_idx = left;
        for (int i = small_idx; i < right; i++){
            if (arr[i] < arr[right]){
                swap(arr, i, small_idx);
                small_idx++;
            }
        }
        swap(arr, small_idx, right);
        return small_idx;
    }

    public static int[] QuickSort(int[] arr, int left, int right){
        if (left < right){
            int pivotIndex = Partition(arr, left, right);
            QuickSort(arr, left, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, right);
        }

        return arr;
    }

    /*
    public static void main(String[] args) {
        int[] arr = new int[200];

        Random random = new Random();

        for (int i = 0; i < arr.length; i++){
            arr[i]  = random.nextInt(400) - 200;
        }

        QuickSort(arr, 0, arr.length - 1);
        BubbleSort b = new BubbleSort();
        SelectionSort s = new SelectionSort();
        b.BubbleSort(arr);


        for (int i : arr) {
            System.out.print(i + "\t");
        }
    } */
}
